//斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： 
//
// F(0) = 0,   F(1) = 1
//F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
// 
//
// 给定 N，计算 F(N)。 
//
// 
//
// 示例 1： 
//
// 输入：2
//输出：1
//解释：F(2) = F(1) + F(0) = 1 + 0 = 1.
// 
//
// 示例 2： 
//
// 输入：3
//输出：2
//解释：F(3) = F(2) + F(1) = 1 + 1 = 2.
// 
//
// 示例 3： 
//
// 输入：4
//输出：3
//解释：F(4) = F(3) + F(2) = 2 + 1 = 3.
// 
//
// 
//
// 提示： 
//
// 
// 0 ≤ N ≤ 30 
// 
// Related Topics 数组 
// 👍 141 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

/**
 * Java：斐波那契数
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P509_FibonacciNumber {
    public static void main(String[] args) {
        Solution solution = new P509_FibonacciNumber().new Solution();
        MyUtil.print(solution.fib(30));
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    ///**
    // * 遍历一遍，不是最优解
    // * 时间复杂度 O(n)
    // * 空间复杂度 O(1)
    // */
    //class Solution {
    //    public int fib(int N) {
    //        if (N < 2) {
    //            return N;
    //        }
    //        int pre = 0, cur = 1, temp;
    //        for (int i = 2; i <= N; i++) {
    //            temp = cur;
    //            cur = pre + cur;
    //            pre = temp;
    //        }
    //        return cur;
    //
    //    }
    //}

    /**
     * 矩阵乘法
     * 时间复杂度 O(longN)
     */
    class Solution {

        public int fib(int N) {
            if (N < 2) {
                return N;
            }
            // 二阶矩阵
            int[][] matrix = {
                    {1, 1},
                    {1, 0}
            };
            int[][] mult = powerMatrix(matrix, N - 2);
            return mult[0][0] + mult[1][0];
        }

        /**
         * 矩阵matrix的n次幂
         * 时间复杂度：O(logN)
         */
        private int[][] powerMatrix(int[][] matrix, int n) {
            // 单位矩阵，斜对角上是1，其他全是0
            int N = matrix.length;
            int[][] res = new int[N][N];
            for (int i = 0; i < N; i++) {
                res[i][i] = 1;
            }
            // 快速求出某个数的n次方
            int[][] t = matrix;
            for (; n != 0; n >>= 1) {
                // n的最后边是1的话就要乘当前的t了
                if ((n & 1) == 1) {
                    res = multMatrix(res, t);
                }
                // t始终乘自己
                t = multMatrix(t, t);
            }
            return res;
        }

        /**
         * 两矩阵相乘
         */
        private int[][] multMatrix(int[][] m1, int[][] m2) {
            int row = m1.length; //结果矩阵的行数
            int col = m2[0].length; // 结果矩阵的列数
            int[][] res = new int[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    for (int k = 0; k < m2.length; k++) {
                        res[i][j] += m1[i][k] * m2[k][j];
                    }
                }
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
